/**
 * 并查集
 * @author ZhengDp
 * @Date 2023/4/22 20:07
 */
public class UnionFind {
    private int count = 0;
    private int[] parent;
    public UnionFind(int n){
        count = n;
        parent = new int[n];
        // 自己指向自己（初始化）
        for(int i =0;i<n;i++) {
            parent[i] = i;
        }
    }

    // 路径压缩
    public int find(int p ) {
        while(p != parent[p]) {
            // 路径压缩
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    public int find2(int p ) {
        int root = p;
        while(root != parent[root]) {
            root = parent[root];
        }
        while(p != parent[p]) {
            int x = p;
            p = parent[p];
            parent[x] = root;
        }
        return root;
    }

    public void union(int p,int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if(rootQ == rootP) {
            return ;
        }
        parent[rootP] = rootQ;
        count--;
    }
}
